package com.zhangx.datastructure.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName Topological
 * @Description 拓扑图  P271
 * 找到任务的顺序
 *
 * @Author zhangx
 * @Date 2021/1/19 8:52
 **/
public class Topological {

    int MAXVEX = 14;
    VertexNode[] adjList = new VertexNode[MAXVEX];
    int numVertexes;//顶点数
    int numEdges;//边数


    /**
     * 边表节点,顶点的出度
     */
    class EdgeNode{
        int weight;
        int adjvex;//在顶点数组中的下标
        EdgeNode next;

        public EdgeNode(int adjvex, EdgeNode next){
            this.adjvex = adjvex;
            this.next = next;
        }
        public EdgeNode(int adjvex){
            this.adjvex = adjvex;
        }

        @Override
        public String toString() {
            return "EdgeNode{" +
                    "weight=" + weight +
                    ", adjvex=" + adjvex +
                    ", next=" + next +
                    '}';
        }
    }
    /**
     * 顶点
     */
    class VertexNode{
        int in;//入节点
        String data;
        EdgeNode firstEdge;

        public VertexNode(String data){
            this.data = data;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "in=" + in +
                    ", data='" + data + '\'' +
                    ", firstEdge=" + firstEdge +
                    '}';
        }
    }

    @Override
    public String toString() {
        for (int i = 0; i < adjList.length; i++) {
            System.out.println(adjList[i]);
        }
        return "Topological{" +
                "MAXVEX=" + MAXVEX +
                ", adjList=" + Arrays.toString(adjList) +
                ", numVertexes=" + numVertexes +
                ", numEdges=" + numEdges +
                '}';
    }

    void init(){
        adjList[0] = fillData("V0",0,11,5,4);
        adjList[1] = fillData("V1",0,8,4,2);
        adjList[2] = fillData("V2",2,9,6,5);
        adjList[3] = fillData("V3",0,13,2,0);
        adjList[4] = fillData("V4",2,7,0,0);
        adjList[5] = fillData("V5",3,12,8,0);
        adjList[6] = fillData("V6",1,5,0,0);
        adjList[7] = fillData("V7",2,0,0,0);
        adjList[8] = fillData("V8",2,7,0,0);
        adjList[9] = fillData("V9",1,11,10,0);
        adjList[10] = fillData("V10",1,13,0,0);
        adjList[11] = fillData("V11",2,0,0,0);
        adjList[12] = fillData("V12",1,9,0,0);
        adjList[13] = fillData("V13",2,0,0,0);
        numVertexes = 14;
    }

    /**
     * 构造链表
     * @param vData
     * @param in
     * @param first
     * @param second
     * @param third
     * @return
     */
    public VertexNode fillData(String vData,int in, int first,int second,int third){
        VertexNode vertexNode = new VertexNode(vData);
        vertexNode.in = in;
        if (first > 0){
            EdgeNode a = new EdgeNode(first);
            if (second > 0){
                EdgeNode b = new EdgeNode(second);
                a.next = b;
                if (third > 0){
                    EdgeNode c = new EdgeNode(third);
                    b.next = c;
                }
            }
            vertexNode.firstEdge = a;
        }
        return vertexNode;
    }

    /**
     * 拓扑排序
     * @return
     */
    String sort(){
        String result = "OK";

        int top = 0;
        int count = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < numVertexes; i++) {

            if (adjList[i].in == 0){
                ++top;
                stack.push(i);
            }
        }
//        不断的在栈中遍历
        while (top!=0){
            top--;
            int gettop = stack.pop();
            System.out.println(adjList[gettop].data);
            count++;
//            循环入度=0的链表
            for (EdgeNode e = adjList[gettop].firstEdge;e!=null;e =e.next){
                int k = e.adjvex;
//                将他们入度-1，就是去除一条连线
                if ((--adjList[k].in)==0){
                    ++top;
//                    如果这个节点的入度=0，加到栈中
                    stack.push(k);//0则入栈
                }
            }

        }
        if (count < numVertexes){
//            所有顶点都输入，就不是环形的，没有回路
            result = "OK";
        }
        return result;
    }

    public static void main(String[] args) {
        Topological topological = new Topological();
        topological.init();
        System.out.println(topological);
        System.out.println(topological.sort());;
    }

}
